package 力扣日常刷题.木23一月.第02天302;

/**
 * @author 帅小伙
 * @date 2022/3/2
 * @description
 */
public class Demo12数组中的逆序对 {


    int[] nums, tmp;

    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return merge(0, nums.length - 1);
    }


    public int merge(int l, int r) {
        if (l >= r) return 0;
        int mid = (l + r) >> 1;
        int res = merge(l, mid) + merge(mid + 1, r);

        int i = l,j = mid+1;

        for (int k = l; k <= r; k++) {
            tmp[k] = nums[k];
        }


        for (int k = l; k <= r; k++) {
            if(i==mid + 1){
                nums[k] = tmp[j++];
            }else if(j == r + 1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{
                nums[k] = tmp[j++];
                res +=(mid - i + 1);
            }
        }
        return res;

    }

}
